#! /usr/bin/python

import math

pan = set(['1', '2', '3', '4', '5', '6', '7', '8', '9'])
MAX = 987654123
def isPrime(n):
    if n == 2 or n == 3 or n == 5 or n == 7: return True
    if n%2 == 0 or n%3 == 0 or n == 1: return False
    for i in range(5, int(math.sqrt(n))+1, 6):
	if n%(i+2) == 0 or n%i == 0: return False
    return True

per = []
def permute():
    for i in range(1, 10):
	for j in range(1, 10):
	    if i == j: continue
	    for k in range(1, 10):
		if k == i or k == j: continue
	        for l in range(1, 10):
		    if l == k or l == i or l == j: continue	
		    for m in range(1, 10):
			if m == l or m == k or m == i or m == j: continue
		        for n in range(1, 10):
			    if n == m or n == l or n == k or n == i or n == j: continue
		            for p in range(1, 10):
			        if p == n or p == m or p == l or p == k or p == i or p == j: continue
		                for q in range(1, 10):
			            if q == p or q == n or q == m or q == l or q == k or q == i or q == j: continue
		                    for x in range(1, 10):					
			                if x == q or x == p or x == n or x == m or x == l or x == k or x == i or x == j: continue
			                per.append([i, j, k, l, m, n, p, q, x])
					

#permute()
#print per

cc = 0
def partition(ll, start):
    i = start
    while (i < 9):
        j = i
	p = 0
	while(j < 9):
	     p = p*10 + ll[j]
	     if isPrime(p):
		#print p
		if j == 8: return True		
		break 
	     j += 1
	i = j + 1

    return False

#print partition([5, 2, 3, 9, 8, 1, 4, 6, 7], 0)
print isPrime(981467)
def partitionOne(ll, start):
    i = start
    count = 0
    while (i < 9):
        j = i
	p = 0
	while(j < 9):
	     p = p*10 + ll[j]
	     if isPrime(p):
		print p, j
		if partition(ll, j+1): count += 1
		if j == 8: 
		   #print pp
		   print "Count", count
		   return True 
	     j += 1
	i = j + 1
    
    return False

print partitionOne([5, 2, 3, 9, 8, 1, 4, 6, 7], 0)

def allPrimes(ll, start):
    i = start
    p = 0
    first = []
    while(i < 9):
	p = p*10 + ll[i]
	if isPrime(p):
	   first.append(i+1)
	   #print p
	i += 1
    #print first
    return first


#print allPrimes([2,3,9,8,1,4,6,7,5], 0)
#print allPart([8, 4, 7, 6, 1, 9, 5, 3, 2], 0)

def findSets(ll):
    total = 0
    i = 0
    while(i < 9):
	first = allPrimes(ll, i)
	if len(first) == 1 and partition(ll, i) and partition(ll, first[0]): 
	   total += 1
	   break
	if first == []: break
	for j in first:
	    if partition(ll, j): total += 1
	#print first, i
	if len(first) > 1:
	   for j in first:
	       if partition(ll, j): total += 1
	i += first.pop()
    return total

#print findSets([5, 2, 3, 9, 8, 1, 4, 6, 7])
#print findSets([8, 4, 7, 6, 1, 9, 5, 3, 2])

count = 0
#for ll in per:
#    count += findSets(ll) 

#print count


